class CBTInserter {
public:
    TreeNode* root;
    queue<TreeNode*> q;
    CBTInserter(TreeNode* root) {
        this->root = root;
        q.push(root);
        while(q.front()->left && q.front()->right){
            TreeNode* node = q.front();
            q.push(node->left);
            q.push(node->right);
            q.pop();
        }
        if(q.front()->left){
            q.push(q.front()->left);
        }
    }
    
    int insert(int v) {
        TreeNode* node = new TreeNode(v);
        TreeNode* cur = q.front();
        if(!cur->left){
            cur->left = node;
        }else{
            cur->right = node;
            q.pop();
        }
        q.push(node);
        return cur->val;
    }
    
    TreeNode* get_root() {
        return root;
    }
};
